package class04;

import java.util.*;

/**
 * 给一个数组，求出这个数组所有小于左数的和，要求时间复杂度 O(n·log n)
 * 例：[1,2,6,4,5] -> 1+(1+2)+(1+2)+(1+2+4)=14
 *
 * <a href="https://leetcode.cn/problems/count-of-smaller-numbers-after-self/">变异版：315. 计算右侧小于当前元素的个数</a>
 */
public class Code02_SmallSum {
    // O(n²) 解法
    public static int way1(int[] arr) {
        int result = 0;
        for (int i = 0; i < arr.length; ++i) {
            for (int j = 0; j < i; ++j) {
                result += arr[j] < arr[i] ? arr[j] : 0;
            }
        }
        return result;
    }

    // O(n·log n) 解法
    public static int way2(int[] arr) {
        return process2(arr, 0, arr.length - 1);
    }

    private static int process2(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return process2(arr, L, M) + process2(arr, M + 1, R) + merge(arr, L, M, R);
    }

    private static int merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0, result = 0;
        int l = L, r = M + 1;
        while (l <= M || r <= R) {
            if (l > M) {
                help[i++] = arr[r++];
            } else if (r > R) {
                help[i++] = arr[l++];
            } else {
                result += arr[l] < arr[r] ? (R - r + 1) * arr[l] : 0;
                help[i++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
            }
        }
        System.arraycopy(help, 0, arr, L, help.length);
        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[(int) (Math.random() * (30 - 1) + 1)];
        for (int i = 0; i < arr1.length; ++i) {
            arr1[i] = (int) (Math.random() * (100 - 1) + 1);
        }
        int[] arr2 = arr1.clone();
        System.out.println(way1(arr1));
        System.out.println(way2(arr2));
    }

    // 力扣原题，变异版解法：315. 计算右侧小于当前元素的个数
    public static class Solution {
        public static class Pair {
            int value;
            int index;

            public Pair(int value, int index) {
                this.value = value;
                this.index = index;
            }
        }

        int[] result;
        Pair[] numsTemp;

        public List<Integer> countSmaller(int[] nums) {
            this.result = new int[nums.length];
            this.numsTemp = new Pair[nums.length];
            for (int i = 0; i < nums.length; ++i) {
                numsTemp[i] = new Pair(nums[i], i);
            }
            process(0, nums.length - 1);
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < nums.length; ++i) {
                res.add(result[i]);
            }
            return res;
        }

        private void process(int L, int R) {
            if (L == R) {
                return;
            }
            int M = L + ((R - L) >> 1);
            process(L, M);
            process(M + 1, R);
            merge(L, M, R);
        }

        private void merge(int L, int M, int R) {
            Pair[] help = new Pair[R - L + 1];
            int i = help.length - 1;
            int l = M;
            int r = R;
            while (l >= L || r >= M + 1) {
                if (l < L) {
                    help[i--] = numsTemp[r--];
                } else if (r < M + 1) {
                    help[i--] = numsTemp[l--];
                } else {
                    result[numsTemp[l].index] = result[numsTemp[l].index] + (numsTemp[l].value > numsTemp[r].value ? r - M : 0);
                    help[i--] = numsTemp[l].value > numsTemp[r].value ? numsTemp[l--] : numsTemp[r--];
                }
            }
            System.arraycopy(help, 0, numsTemp, L, help.length);
        }
    }
}
